package com.dexter.year2023.charpter4_stack.level2.topic2_3最大栈;

import java.util.Stack;

/**
 * LeetCode 716. 最大栈
 * https://leetcode.cn/problems/max-stack/ 🔒
 * <p>
 * 设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。
 * 实现 MaxStack 类:
 * MaxStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * int pop() 移除堆栈顶元素并返回这个元素。
 * int top() 返回堆栈顶元素，无需移除。
 * int peekMax() 检索并返回堆栈中的最大元素，无需移除。
 * int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近堆栈顶 的那个。
 *
 * @author Dexter
 */
class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> maxStack;

    public MaxStack() {
        stack = new Stack<>();
        maxStack = new Stack<>();
    }

    // 入栈
    public void push(int val) {
        stack.push(val);
        int max = maxStack.empty() ? val : maxStack.peek();
        maxStack.push(Math.max(val, max));
    }

    // 出栈
    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    // 栈顶
    public int top() {
        return stack.peek();
    }

    // 获取maxStack栈顶
    public int peekMax() {
        return maxStack.peek();
    }

    // maxStack移除最大值
    public int popMax() {
        // maxStack的栈顶，也是当前最大值，但在stack中不一定是栈顶
        int max = peekMax();
        // buffer用于保存stack中max上方的元素
        Stack<Integer> buffer = new Stack();
        while (top() != max) {
            // 入栈
            buffer.push(pop());
        }
        // 找到了，在stack和maxStack中移除max
        pop();
        // 再把暂存的元素放回stack
        while (!buffer.empty()) {
            // 这里push包含了在maxStack中同步更新最大值
            push(buffer.pop());
        }
        return max;
    }
}
